\section{Implementación}

La implementación del algoritmo Touch Count fue realizada en Java, como parte de la base de datos con fines académicos de la cátedra. El algoritmo de Touch Count se implementó como un objeto de la clase \textit{TouchCountReplacementStrategy}, siendo éste utilizado por el \textit{Buffer Pool}, que es un objeto que implementa la interfaz \textit{BufferPool}

\subsection{Lista de buffers}

Decidimos utilizar, en vez de una lista con un puntero a la separación entre las secciones, dos listas separadas que tienen los elementos \textit{cold} y \textit{hot} cada una. La lista \textit{cold} tiene el extremo LRU (los más fríos) en su comienzo, y la lista \textit{hot} tiene en su final los más populares (los más calientes).

\subsection{Elección de Víctima}

Al pedírsele una víctima a la estrategia, en primer lugar buscamos si en la lista \textit{cold} hay elementos con count mayor a 2. A éstos los mandamos al extremo \textit{hot} de la lista, antes seteándoles el \textit{count} a 0. En esta primera etapa, no reordenamos elementos que hayan estado previamente en la lista \textit{hot}.

Luego de ésto, balanceamos las listas. Como sólo agregamos elementos a la lista \textit{hot}, lo que tenemos que hacer es "bajar" elementos de dicha lista al final de la \textit{cold list}. Ésto lo hacemos hasta que se balanceen las listas, y seteando a cada buffer descendido su count a 1.

Finalmente, luego de ésto, se elige el primer buffer de la lista cold que no se encuentre lockeado (es decir, que su \textit{pin count} sea 0)

\subsection{Código}

\subsubsection{Buffer Frame}
\begin{lstlisting}[language=java, breaklines=true]
package ubadb.core.components.bufferManager.bufferPool.replacementStrategies.touchcount;

import java.util.Date;

import ubadb.core.components.bufferManager.bufferPool.BufferFrame;
import ubadb.core.common.Page;
import ubadb.core.exceptions.BufferFrameException;

public class TouchBufferFrame extends BufferFrame {
	private int count;
	private Date lastTouch;
	
	public TouchBufferFrame(Page page) {
		super(page);
		count = 0;
		lastTouch = new Date();
	}

	public void unpin() throws BufferFrameException {
		super.unpin();
		Date tempDate = new Date();
		
		if (((tempDate.getTime()-lastTouch.getTime())/1000)>=3)
		{
			lastTouch = tempDate;
			count++;
		}
	}
	
	public int getCount()
	{
		return count;
	}
	
	public void setCount(int i) {
		count = i;
		
	}
}

\end{lstlisting}

\subsubsection{Estrategia}
\begin{lstlisting}[language=java, breaklines=true]
package ubadb.core.components.bufferManager.bufferPool.replacementStrategies.touchcount;

import java.util.Collection;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Vector;

import java.util.Iterator;

import ubadb.core.common.Page;
import ubadb.core.components.bufferManager.bufferPool.BufferFrame;
import ubadb.core.components.bufferManager.bufferPool.replacementStrategies.PageReplacementStrategy;
import ubadb.core.exceptions.BufferFrameException;
import ubadb.core.exceptions.PageReplacementStrategyException;

public class TouchCountReplacementStrategy implements PageReplacementStrategy {
	private LinkedList<TouchBufferFrame> cold;
	private LinkedList<TouchBufferFrame> hot;
	private int bufferSize;
	private static String NAME = "TouchCount";
	
	public BufferFrame findVictim(Collection<BufferFrame> bufferFrames) throws PageReplacementStrategyException {
		if (bufferSize == 0) {
			initialize(bufferFrames);
		}
		
		LookForHotFrames();
		BalanceColdAndHot();
		
		TouchBufferFrame victim = popFirstUnpinnedCold();
		return victim;
	}
	
	private TouchBufferFrame popFirstUnpinnedCold() throws PageReplacementStrategyException {
		Iterator<TouchBufferFrame> it = cold.iterator();
		
		while (it.hasNext())
		{
			TouchBufferFrame frame = it.next();
			if (frame.canBeReplaced())
			{
				it.remove();
				return frame;
			}
		}
		throw new PageReplacementStrategyException("There is no unpinned cold frame");
	}

	private void BalanceColdAndHot() throws PageReplacementStrategyException {
		while (!queuesAreBalanced())
			coolLastHotFrame();
	}

	private void LookForHotFrames() {
		Iterator<TouchBufferFrame> iterator = cold.iterator();
		Collection<TouchBufferFrame> coldsToRemove = new LinkedList<TouchBufferFrame>();
		
		while (iterator.hasNext()) {
			TouchBufferFrame frame = (TouchBufferFrame)iterator.next();
			if (frame.getCount()>2){
				frame.setCount(0);
				hot.addLast(frame);
				coldsToRemove.add(frame);
			}
		}
		
		cold.removeAll(coldsToRemove);
	}

	private void initialize(Collection<BufferFrame> bufferFrames) {
		bufferSize = bufferFrames.size();
		Iterator<BufferFrame> iterator = bufferFrames.iterator();

		hot = new LinkedList<TouchBufferFrame>();
		cold = new LinkedList<TouchBufferFrame>();
		int count = 0;
		while (iterator.hasNext())
		{
			TouchBufferFrame frame = (TouchBufferFrame)iterator.next();
			
			if (count < (bufferSize/2) )
				hot.addFirst(frame);
			else
				cold.addFirst(frame);
			++count;
		}
	}
	
	private void coolLastHotFrame() throws PageReplacementStrategyException {
		if (hot.size()>0)
		{
			TouchBufferFrame frame = hot.removeFirst();
			frame.setCount(1);
			cold.addLast(frame);
		}
		else throw new PageReplacementStrategyException("There is no hot frame!");
	}

	private boolean queuesAreBalanced() {
		return Math.abs(hot.size() - cold.size()) <= 1;
	}

	public BufferFrame createNewFrame(Page page) {
		TouchBufferFrame newFrame = new TouchBufferFrame(page);
		
		if (bufferSize != 0) {
			cold.addLast(newFrame);
		}
		
		return newFrame;
	}
	
	public String toString() {
		return NAME;
	}
}
\end{lstlisting}
